package source.arrayAndString;

import org.junit.Test;

import java.util.*;

public class ArrayAndString {
    /**
     * 合并两个有序数组
     * <p>
     * 给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，
     * 另有两个整数 m 和 n ，
     * 分别表示 nums1 和 nums2 中的元素数目。
     * <p>
     * 请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。
     * <p>
     * 注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。
     * 为了应对这种情况，nums1 的初始长度为 m + n，
     * 其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。
     * nums2 的长度为 n 。
     */
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int len1 = m - 1, len2 = n - 1, len = m + n - 1;

        while (len1 >= 0 && len2 >= 0) {
            nums1[len--] = nums1[len1] <= nums2[len2] ? nums2[len2--] : nums1[len1--];
        }
        System.arraycopy(nums2, 0, nums1, 0, len2 + 1);
    }

    /**
     * 移除元素
     * <p>
     * 给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素。
     * 元素的顺序可能发生改变。然后返回 nums 中与 val 不同的元素的数量。
     * <p>
     * 假设 nums 中不等于 val 的元素数量为 k，要通过此题，您需要执行以下操作：
     * <p>
     * 更改 nums 数组，使 nums 的前 k 个元素包含不等于 val 的元素。
     * nums 的其余元素和 nums 的大小并不重要。
     * <p>
     * 返回 k。
     */
    public int removeElement(int[] nums, int val) {
        int k = 0;

        int j = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != val) {
                nums[j++] = nums[i];
            } else
                k++;

        }

        return k;
    }

    /**
     * 删除有序数组中的重复项
     * <p>
     * 给你一个 非严格递增排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。
     * 元素的 相对顺序 应该保持 一致 。
     * 然后返回 nums 中唯一元素的个数。
     * <p>
     * 考虑 nums 的唯一元素的数量为 k ，你需要做以下事情确保你的题解可以被通过：
     * <p>
     * 更改数组 nums ，使 nums 的前 k 个元素包含唯一元素，并按照它们最初在 nums 中出现的顺序排列。
     * nums 的其余元素与 nums 的大小不重要。
     * <p>
     * 返回 k 。
     */
    public int removeDuplicates(int[] nums) {
        int k = 0;
        for (int i = 0; i < nums.length - 1; i++) {
            if (nums[k] != nums[i + 1]) {
                nums[++k] = nums[i + 1];
            }
        }
        return k + 1;
    }

    /**
     * 删除有序数组中的重复项 II
     * <p>
     * 给你一个有序数组 nums ，请你 原地 删除重复出现的元素，使得出现次数超过两次的元素只出现两次 ，返回删除后数组的新长度。
     * <p>
     * 不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。
     */
    public int removeDuplicates2(int[] nums) {
        int k = 0;

        for (int i = 0; i < nums.length - 2; i++) {
            if (nums[k] != nums[i + 2]) {
                nums[k + 2] = nums[i + 2];
                k++;
            }
        }


        return k + 1;
    }

    /**
     * 多数元素
     * <p>
     * 给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
     * <p>
     * 你可以假设数组是非空的，并且给定的数组总是存在多数元素。
     */


    /**
     * 轮转数组
     * <p>
     * 给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。
     */
    public static void rotate(int[] nums, int k) {
        int j = nums.length - 1;
        reverse(nums, 0, j);
        reverse(nums, 0, (k - 1) % (j + 1));
        reverse(nums, k % (j + 1), j);
    }

    /**
     * 翻转数组 nums 索引 i 到 j
     *
     * @param nums 输入数组
     * @param i    起始索引
     * @param j    终止索引
     */
    public static void reverse(int[] nums, int i, int j) {
        if (i < j) {
            int tmp;
            while (i < j) {
                tmp = nums[i];
                nums[i] = nums[j];
                nums[j] = tmp;
                i++;
                j--;
            }
        }
    }

    /**
     * 买卖股票的最佳时机
     * <p>
     * 给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
     * <p>
     * 你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。
     * <p>
     * 设计一个算法来计算你所能获取的最大利润。
     * <p>
     * 返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。
     *
     * @param prices 股票行情
     * @return 最大利润
     */
    public int maxProfit(int[] prices) {
        int minPrice = prices[0], maxProfit = 0;
        for (int price : prices) {
            if (minPrice > price) {
                minPrice = price;
            } else if (maxProfit < price - minPrice)
                maxProfit = price - minPrice;
        }
        return maxProfit;
    }

    /**
     * 买卖股票的最佳时机 II
     * 给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。
     * <p>
     * 在每一天，你可以决定是否购买和/或出售股票。
     * 你在任何时候 最多 只能持有 一股 股票。你也可以先购买，然后在 同一天 出售。
     * <p>
     * 返回 你能获得的 最大 利润 。
     *
     * @param prices 已知股票行情
     * @return 最大利润
     */
    public int maxProfitII(int[] prices) {
        int ans = 0;
        int n = prices.length;
        for (int i = 1; i < n; ++i) {
            ans += Math.max(0, prices[i] - prices[i - 1]);
        }
        return ans;
    }

    /**
     * 跳跃游戏
     * <p>
     * 给你一个非负整数数组 nums ，你最初位于数组的 第一个下标 。
     * 数组中的每个元素代表你在该位置可以跳跃的最大长度。
     * <p>
     * 判断你是否能够到达最后一个下标，如果可以，返回 true ；否则，返回 false 。
     */
    public boolean canJump(int[] nums) {

        int maxJump = 0;
        for (int i = 0; i < nums.length; i++) {
            if (maxJump >= nums.length - 1) {
                return true;
            } else if (maxJump < i)
                return false;
            maxJump = Math.max(nums[i] + i, maxJump);

        }
        return false;
    }

    /**
     * 跳跃游戏 II
     * <p>
     * 给定一个长度为 n 的 0 索引整数数组 nums。
     * 初始位置为 nums[0]。
     * <p>
     * 每个元素 nums[i] 表示从索引 i 向后跳转的最大长度。
     * 换句话说，如果你在 nums[i] 处，你可以跳转到任意 nums[i + j] 处:
     * <p>
     * 0 <= j <= nums[i]
     * i + j < n
     * 返回到达 nums[n - 1] 的最小跳跃次数。
     * <p>
     * 生成的测试用例可以到达 nums[n - 1]。
     */
    public int jump(int[] nums) {
        int position = nums.length - 1;
        int steps = 0;
        while (position > 0) {
            for (int i = 0; i < position; i++) {
                if (i + nums[i] >= position) {
                    position = i;
                    steps++;
                }
            }
        }
        return steps;
    }

    public int jump2(int[] nums) {
        int end = nums[0];
        int maxPosition = 0;
        int steps = 0;
        for (int i = 0; i < nums.length - 1; i++) {
            maxPosition = Math.max(maxPosition, i + nums[i]);
            if (end == i) {
                end = maxPosition;
                steps++;
            }

        }
        return steps;
    }

    /**
     * 给你一个整数数组 citations ，其中 citations[i] 表示研究者的第 i 篇论文被引用的次数。计算并返回该研究者的 h 指数。
     * <p>
     * 根据维基百科上 h 指数的定义：
     * h 代表“高引用次数” ，一名科研人员的 h 指数 是指他（她）至少发表了 h 篇论文，并且 至少 有 h 篇论文被引用次数大于等于 h 。
     * 如果 h 有多种可能的值，h 指数 是其中最大的那个。
     */
    public int hIndex(int[] citations) {
        int n = citations.length + 1;
        int[] count = new int[n];
        int totol = 0;
        for (int i = 0; i < n - 1; i++) {
            if (citations[i] >= n - 1)
                count[n - 1]++;
            else
                count[citations[i]]++;
        }
        for (int i = n - 2; i >= 0; i--) {
            totol += count[i];
            if (totol > i) {
                return totol;
            }

        }
        return totol;
    }

    /**
     * 除自身以外数组的乘积
     * 给你一个整数数组 nums，返回 数组 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。
     * <p>
     * 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在  32 位 整数范围内。
     * <p>
     * 请 不要使用除法，且在 O(n) 时间复杂度内完成此题。
     *
     * @param nums 原始数组
     * @return answer 返回除自身以外的数组的乘积
     */
    public int[] productExceptSelf(int[] nums) {
        int[] answer = new int[nums.length];
        int tmp = 1;
        for (int i = 0; i < nums.length; i++) {
            answer[i] = tmp;
            tmp *= nums[i];
        }
        tmp = 1;
        for (int i = nums.length - 1; i >= 0; i--) {
            answer[i] = tmp;
            tmp *= nums[i];
        }
        return answer;
    }

    /**
     * 在一条环路上有 n 个加油站，其中第 i 个加油站有汽油 gas[i] 升。
     * <p>
     * 你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。
     * 你从其中的一个加油站出发，开始时油箱为空。
     * <p>
     * 给定两个整数数组 gas 和 cost ，如果你可以按顺序绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1 。
     * 如果存在解，则 保证 它是 唯一 的。
     *
     * @param gas  第 i 个加油站有汽油 gas[i] 升。
     * @param cost 从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升
     * @return 可以按顺序绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1 。
     */
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int n = gas.length;
        int max = 0;
        int sum = max;
        int index = 0;
        for (int i = 0; i < n; i++) {
            cost[i] = gas[i] - cost[i];
            sum += cost[i];
            if (max > sum) {
                max = sum;
                index = i;
            }
        }
        return sum < 0 ? -1 : (index + 1) % n;
    }

    /**
     * n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。
     * <p>
     * 你需要按照以下要求，给这些孩子分发糖果：
     * <p>
     * 每个孩子至少分配到 1 个糖果。
     * 相邻两个孩子评分更高的孩子会获得更多的糖果。
     * 请你给每个孩子分发糖果，计算并返回需要准备的 最少糖果数目 。
     *
     * @param ratings 每个孩子的评分
     * @return 最少所需糖果数量
     */
    public int candy(int[] ratings) {
        int sum = 0, right = 0;
        int[] left = new int[ratings.length];
        left[0] = 1;
        for (int i = 0; i < ratings.length; i++) {
            if (i > 0 && ratings[i - 1] < ratings[i]) {
                left[i] = left[i - 1] + 1;
            } else
                left[i] = 1;
        }
        for (int i = ratings.length - 1; i >= 0; i--) {
            if (i < ratings.length - 1 && ratings[i] > ratings[i + 1]) {
                right++;
                ;
            } else
                right = 1;
            sum += Math.max(left[i], right);
        }

        return sum;
    }

    /**
     * 给你一个字符串 s，由若干单词组成，单词前后用一些空格字符隔开。
     * 返回字符串中 最后一个 单词的长度。
     * <p>
     * 单词 是指仅由字母组成、不包含任何空格字符的最大子字符串。
     *
     * @param s 原始字符串
     * @return 最后一个单词的长度
     */
    public static int lengthOfLastWord(String s) {
        int right = s.length() - 1;
        while (right > 0 && s.charAt(right) == ' ') {
            right--;
        }
        int left = right;
        while (left >= 0 && s.charAt(left) != ' ') {
            left--;
        }
        return right - left;
    }

    /**
     * 最长公共前缀
     * <p>
     * 编写一个函数来查找字符串数组中的最长公共前缀。
     *
     * @param strs 字符串数组
     * @return 最长公共前缀，如果不存在公共前缀，返回空字符串 ""。
     */
    public String longestCommonPrefix(String[] strs) {
        int minLength = strs[0].length();
        for (int j = 1; j < strs.length; j++) {
            minLength = Math.min(minLength, strs[j].length());
        }
        String subString = "";
        for (int i = 0; i < minLength; i++) {
            for (int j = 1; j < strs.length; j++) {
                if (strs[j - 1].charAt(i) != strs[j].charAt(i))
                    return subString;
            }
            subString += strs[0].charAt(i);
        }
        return subString;
    }

    /**
     * 多数元素
     * <p>
     * 给定一个大小为 n 的数组 nums ，返回其中的多数元素。
     * 多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
     * <p>
     * 你可以假设数组是非空的，并且给定的数组总是存在多数元素。
     *
     * @param nums 输入数组
     * @return 多数元素
     */
    public int majorityElement(int[] nums) {
        int count = 0;
        int candidate = 0;
        for (int num : nums) {
            if (count == 0) {
                candidate = num;
            }
            count += (candidate == num ? 1 : -1);
        }

        return candidate;
    }

    /**
     * 反转字符串中的单词
     * <p>
     * 给你一个字符串 s ，请你反转字符串中 单词 的顺序。
     * <p>
     * 单词 是由非空格字符组成的字符串。
     * s 中使用至少一个空格将字符串中的 单词 分隔开。
     * <p>
     * 返回 单词 顺序颠倒且 单词 之间用单个空格连接的结果字符串。
     * <p>
     * 注意：输入字符串 s中可能会存在前导空格、尾随空格或者单词间的多个空格。
     * 返回的结果字符串中，单词间应当仅用单个空格分隔，且不包含任何额外的空格。
     *
     * @param s 输入字符串
     * @return 结果字符串
     */
    public String reverseWords(String s) {
        String[] str = s.split(" ");
        s = "";
        boolean isFirst = true;
        for (int i = str.length - 1; i >= 0; i--) {
            if (!str[i].isEmpty()) {
                if (isFirst) {
                    s += str[i];
                    isFirst = false;
                    continue;
                }
                s += (" " + str[i]);
            }
        }
        return s;
    }

    /**
     * Z
     *
     * @param s       输入
     * @param numRows 行数
     * @return 排序后的字符串
     */
    public String convert(String s, int numRows) {
        if (numRows == 1)
            return s;
        String string = "";
        int everyNum = numRows * 2 - 2;
        int j;

        for (int i = 0; i < numRows; i++) {
            j = i;
            while (j < s.length()) {
                string += s.charAt(j);
                if (j % everyNum > 0 && j % everyNum < numRows - 1 && j - i + everyNum - i < s.length()) {
                    string += s.charAt(j - i + everyNum - i);

                }
                j += everyNum;
            }
        }


        return string;
    }

    /**
     * KMP
     * 模式匹配算法
     *
     * @param haystack 主串
     * @param needle   模式串
     * @return haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。
     * 如果 needle 不是 haystack 的一部分，则返回  -1 。
     */
    public int strStr(String haystack, String needle) {
        boolean match = true;
        for (int i = 0; i <= haystack.length() - needle.length(); i++) {
            match = true;
            for (int j = 0; j < needle.length(); j++) {
                if (haystack.charAt(i + j) != needle.charAt(j)) {
                    match = false;
                    break;
                }
            }
            if (match) {
                return i;
            }
        }
        return -1;
    }

    /**
     * 接雨水
     * 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，
     * 计算按此排列的柱子，下雨之后能接多少雨水。
     *
     * @param height n 个非负整数表示每个宽度为 1 的柱子的高度
     * @return 接多少雨水
     */
    public int trap(int[] height) {
        int length = height.length;
        int[] leftMax = new int[length];
        int[] rightMax = new int[length];
        leftMax[0] = height[0];
        for (int i = 1; i < length; i++) {
            leftMax[i] = Math.max(leftMax[i - 1], height[i]);
        }

        rightMax[length - 1] = height[length - 1];
        for (int i = length - 2; i >= 0; i--) {
            rightMax[i] = Math.max(rightMax[i + 1], height[i]);
        }

        int sum = 0;
        for (int i = 0; i < length; i++) {
            sum += Math.min(leftMax[i], rightMax[i]) - height[i];
        }
        return sum;
    }

    /**
     * 罗马数字转整数
     * <p>
     * 罗马数字包含以下七种字符: I， V， X， L，C，D 和 M。
     * 字符          数值
     * I             1
     * V             5
     * X             10
     * L             50
     * C             100
     * D             500
     * M             1000
     * 例如， 罗马数字 2 写做 II ，即为两个并列的 1 。
     * 12 写做 XII ，即为 X + II 。 27 写做  XXVII, 即为 XX + V + II 。
     * 通常情况下，罗马数字中小的数字在大的数字的右边。
     * 但也存在特例，例如 4 不写做 IIII，而是 IV。
     * 数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。
     * 同样地，数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况：
     * I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。
     * X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。
     * C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。
     * 给定一个罗马数字，将其转换成整数。
     *
     * @param s 罗马数字
     * @return 整数
     */
    public int romanToInt(String s) {
        int sum = 0;
        int value = 0;
        for (int i = 0; i < s.length(); i++) {
            value = this.value.get(s.charAt(i));
            if (i < s.length() - 1 && value < this.value.get(s.charAt(i + 1))) {
                sum -= value;
            } else
                sum += value;
        }
        return sum;
    }

    Map<Character, Integer> value = new HashMap<>() {
        {
            put('I', 1);
            put('V', 5);
            put('X', 10);
            put('L', 50);
            put('C', 100);
            put('D', 500);
            put('M', 1000);
        }
    };

    /**
     * 整数转罗马数字
     */
    public String intToRoman(int num) {
        int[] value = new int[]{1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
        String[] symbol = new String[]{"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};
        StringBuilder stringBuilder = new StringBuilder();
        int i = 0;
        while (num > 0) {
            if (num >= value[i]) {
                num -= value[i];
                stringBuilder.append(symbol[i]);
            } else {
                i++;
            }
        }
        return stringBuilder.toString();
    }

    @Test
    public void testRoman() {
        System.out.println(intToRoman(1994));
//        new StringBuilder().
    }

    /**
     * 文本左右对齐
     * <p>
     * 给定一个单词数组 words 和一个长度 maxWidth ，重新排版单词，使其成为每行恰好有 maxWidth 个字符，且左右两端对齐的文本。
     * 你应该使用 “贪心算法” 来放置给定的单词；
     * 也就是说，尽可能多地往每行中放置单词。必要时可用空格 ' ' 填充，使得每行恰好有 maxWidth 个字符。
     * 要求尽可能均匀分配单词间的空格数量。
     * 如果某一行单词间的空格不能均匀分配，则左侧放置的空格数要多于右侧的空格数。
     * 文本的最后一行应为左对齐，且单词之间不插入额外的空格。
     * 注意:
     * 单词是指由非空格字符组成的字符序列。
     * 每个单词的长度大于 0，小于等于 maxWidth。
     * 输入单词数组 words 至少包含一个单词。
     *
     * @param words    输入单词数组
     * @param maxWidth 排版要求行宽
     * @return list<每行字符串>
     */
    public List<String> fullJustify(String[] words, int maxWidth) {
        List<String> list = new ArrayList<>();
        StringBuilder s = new StringBuilder();
        int len;
        int startIndex;
        int spaceNum = 0, wordsNum;
        for (int i = 0; i < words.length; i++) {
            len = 0;
            startIndex = i;
            wordsNum = 0;
            for (int j = i; j < words.length; j++) {
                len += (words[j].length() + 1);
                if (len > maxWidth + 1) {
                    spaceNum = maxWidth - (len - wordsNum - words[j].length() - 1);
                    i = j - 1;
                    break;
                }
                wordsNum++;
                spaceNum = maxWidth - (len - wordsNum);
            }
            if (startIndex + wordsNum >= words.length) {

                for (int k = startIndex; k < startIndex + wordsNum - 1; k++) {
                    words[k] += " ";
                    spaceNum--;
                }
                for (int k = 0; k < spaceNum; k++) {
                    words[startIndex + wordsNum - 1] += " ";
                }
                for (int j = startIndex; j < startIndex + wordsNum; j++) {
                    s.append(words[j]);
                }
                list.add(String.valueOf(s));
                break;
            }
            for (int j = 0; j < spaceNum && wordsNum > 0; j++) {
                if (wordsNum == 1) {
                    while (words[startIndex].length() < maxWidth)
                        words[startIndex] += " ";
                    break;
                }
                words[startIndex + j % (wordsNum - 1)] += " ";
            }

            for (int j = startIndex; j < startIndex + wordsNum; j++) {
                s.append(words[j]);
            }
            list.add(String.valueOf(s));
            s.setLength(0);
        }
        return list;
    }

    @Test
    public void testFullJustify() {
        String[] str = new String[]{"This", "is", "an", "example", "of", "text", "justification."};
        List<String> list = fullJustify(str, 16);
        for (String s :
                list) {
            System.out.println(s);
        }
    }

    @Test
    public void test() {
        int[] nums = {1, 20, 3};

        Arrays.sort(nums);

        System.out.println(Arrays.toString(nums));
    }
}






